home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / ui / del.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-03-07  |  7.3 KB  |  301 lines
  1. /**
  2.    GRAB Graph Layout and Browser System
  3.  
  4.    Copyright (c) 1986, 1988 Regents of the University of California
  5.    Copyright (c) 1989, Tera Computer Company
  6.  **/
  7.  
  8.   /** 
  9.      routines for deletions 
  10.  
  11.      The tricky parts of deletions mostly are due to dummy nodes.  If
  12.      an edge is deleted and one endpoint is a dummy node, the whole edge
  13.      must be eliminated.
  14.  
  15.      If a node is deleted, all edges from it must be deleted.
  16.  
  17.      If a dummy node is deleted, simply 'straighten' the edge so that
  18.      the dummy's previous node connects directly to the dummy's next node.
  19.  
  20.      Multiple edges are also a problem:  If you delete a dummy node that 
  21.      handles multiple edges, all those edges must be straightened.  
  22.      If you delete an edge, you must check whether there is still an edge
  23.      left between the two nodes, and if not, links and outedge must be 
  24.      removed.
  25.    **/
  26.  
  27. #include "digraph.h"
  28. #include "globals.h"
  29. #include "interf.h"
  30. #include "tedge.h"
  31.  
  32. OUTEDGE *get_edge();
  33. NODE *DeleteFromDummyNodes(), *DeleteToDummyNodes();
  34.  
  35. void DoSDeleteNode()
  36.   /**
  37.      Delete the node the cursor is pointing to.
  38.  
  39.      First, eliminate it from the screen.
  40.      Then, delete it from the data structure.
  41.    **/
  42. {
  43.     NODE *node;
  44.  
  45.     if ((node = (NODE *) ICurNode()) == NULL) 
  46.     {
  47.         IChangeStatusLine("No node under cursor", FALSE);
  48.         return;
  49.     }
  50.  
  51.       /* delete it from the screen */
  52.     ScrDeleteNode(digraph, node);
  53.  
  54.       /* delete it from the digraph data structure */
  55.     if (Is_dummy(node)) 
  56.     {
  57.         DeleteDummy(digraph, node);
  58.     }
  59.     else 
  60.     {
  61.         DeleteNode(digraph, node);
  62.     }
  63.  
  64.     IChangeStatusLine("Node Deleted", FALSE);
  65.     graphChanged = TRUE;
  66.     ckpt_done = FALSE;
  67. }
  68.  
  69. void DoSDeleteArc()
  70.   /**
  71.      Delete the edge the cursor is pointing to
  72.  
  73.      First, eliminate it from the screen.
  74.      Then, eliminate it from the digraph data structure.
  75.    **/
  76. {
  77.     NODE *top, *bot;
  78.     NODE *from, *to;
  79.     TEDGE *edge;
  80.  
  81.     edge = (TEDGE *) ICurEdge();
  82.     from = (NODE *) edge->fromnode;
  83.     to = (NODE *) edge->tonode;
  84.  
  85.       /* delete the edge from the screen */
  86.     ScrDeleteEdge(digraph, from, to, edge->ord, &top, &bot);
  87.  
  88.       /* delete the edge from digraph */
  89.     DeleteEdge(digraph, top, bot, edge->ord);
  90.  
  91.     IChangeStatusLine("Arc Deleted", FALSE);
  92.     graphChanged = TRUE;
  93.     ckpt_done = FALSE;
  94. }
  95.  
  96. extern NODE *prev_dummy();
  97. extern NODE *next_dummy();
  98.  
  99. DeleteDummy(digraph, node)
  100. DIGRAPH *digraph;
  101. NODE *node;
  102.   /** 
  103.      To delete a dummy, 'straighten' the edge so it runs directly
  104.      from the dummy's previous node to the dummy's next node.  Of course,
  105.      if the dummy had multiple edges, you must do it for all of them.
  106.  
  107.      The edges out of the dummy have already been deleted, so all that
  108.      must be done is to add the edges, remove the old link, and add the 
  109.      proper link.
  110.    **/
  111. {
  112.     NODE *prev, *next, *prev_dummy(), *next_dummy();
  113.     OUTEDGE *e;
  114.     int i;
  115.  
  116.     prev = prev_dummy(digraph, node);
  117.     next = next_dummy(digraph, node);
  118.  
  119.     for (i = max_edges(prev, next); i > 0; i--)
  120.     {
  121.     if ((e = get_edge(digraph, prev, next, i)) != NULL)
  122.     {
  123.             draw_edge (digraph, e, prev, next, i, &screen, TRUE);
  124.     }
  125.     }
  126.  
  127.     remove_link(prev, node);
  128.     remove_link(node, next);
  129.  
  130.     if (prev != next) 
  131.       /**
  132.      I don't believe this will ever be false.
  133.      That would imply an edge from a node to itself
  134.        **/
  135.     {
  136.         add_element(Succ_set(prev), Vno(next));
  137.         add_element(Ante_set(next), Vno(prev));
  138.     }
  139.  
  140.     dispose_node(digraph, node);
  141. }
  142.  
  143. NODE *get_next_node();
  144. NODE *prev_dummy(), *next_dummy();
  145.  
  146. ScrDeleteNode(digraph, node)
  147. DIGRAPH *digraph;
  148. NODE *node;
  149.   /* ScrDeleteNode removes a node from the screen, including all edges */
  150. {
  151.     VNO prev_vno, next_vno;
  152.     NODE *dummy, *prevnode, *nextnode;
  153.     int i;
  154.    
  155.     if (Is_dummy(node))
  156.       /* just remove edges out of the node */
  157.     {
  158.         each_element(Ante_set(node), prev_vno)
  159.         loop
  160.         prevnode = Node(digraph, prev_vno);
  161.  
  162.         for (i = max_edges(prevnode, node); i > 0; i--)
  163.         {
  164.         if (get_edge(digraph, prevnode, node, i) != NULL)
  165.         {
  166.                     IDelEdge((char *) prevnode, (char *) node, i);
  167.         }
  168.         }
  169.         endloop
  170.     
  171.         each_element(Succ_set(node), next_vno)
  172.         loop
  173.         nextnode = Node(digraph, prev_vno);
  174.  
  175.         for (i = max_edges(node, nextnode); i > 0; i--)
  176.         {
  177.         if (get_edge(digraph, node, nextnode, i) != NULL)
  178.         {
  179.                     IDelEdge((char *) node, (char *) nextnode, i);
  180.         }
  181.         }
  182.         endloop
  183.     }
  184.     else
  185.       /** 
  186.          remove ancestor dummy nodes and edges.
  187.          remove successor dummy nodes and edges.
  188.        **/
  189.     {
  190.         each_element(Ante_set(node), prev_vno)
  191.         loop
  192.         prevnode = Node(digraph, prev_vno);
  193.  
  194.         for (i = max_edges(prevnode, node); i > 0; i--)
  195.         {
  196.         if (get_edge(digraph, prevnode, node, i) != NULL)
  197.         {
  198.                     scr_remove_ante_links(digraph, node, prevnode, i, &dummy);
  199.         }
  200.         }
  201.         endloop
  202.  
  203.         each_element(Succ_set(node), next_vno)
  204.         loop
  205.         nextnode = Node(digraph, next_vno);
  206.  
  207.         for (i = max_edges(node, nextnode); i > 0; i--)
  208.         {
  209.         if (get_edge(digraph, node, nextnode, i) != NULL)
  210.         {
  211.                     scr_remove_succ_links(digraph, node, nextnode, i, &dummy);
  212.         }
  213.         }
  214.         endloop
  215.     }
  216.  
  217.     IDelNode((char *) node, -1);  /* erase node from screen */
  218. } /* ScrDeleteNode */
  219.  
  220. ScrDeleteEdge(digraph, from_node, to_node, ord, top, bot)
  221. DIGRAPH *digraph;
  222. NODE *from_node, *to_node;
  223. int ord;
  224. NODE **top, **bot;
  225.   /** 
  226.      remove ancestor dummy nodes and edges
  227.      remove successor dummy nodes and edges
  228.      return the endpoints of the edge in top and bot
  229.    **/
  230. {
  231.       /* this also removes the current edge */
  232.     scr_remove_ante_links (digraph, to_node, from_node, ord, top);
  233.  
  234.     if (Is_dummy(to_node))
  235.     {
  236.     scr_remove_succ_links (digraph, to_node, next_dummy(digraph, to_node), 
  237.                    ord, bot);
  238.     IDelNode((char *) to_node, ord);
  239.     }
  240.     else
  241.     {
  242.     *bot = to_node;
  243.     }
  244. } /* ScrDeleteEdge */
  245.  
  246. scr_remove_ante_links(digraph, node, prev_node, ord, top)
  247. DIGRAPH *digraph;
  248. NODE *node, *prev_node;
  249. int ord;
  250. NODE **top;
  251.   /**
  252.      scr_remove_ante_links follows the chain of ancestor edges from node 
  253.      through prev through the prev non-dummy node, deleting all edges and 
  254.      dummy nodes along the way.  When done, it sets top to the prev non-dummy 
  255.      node.  
  256.    **/
  257. {
  258.     NODE *curr, *prev;
  259.  
  260.     IDelEdge((char *) prev_node, (char *) node, ord);
  261.     curr = prev_node;
  262.  
  263.     while (Is_dummy(curr))
  264.     {
  265.         prev = prev_dummy(digraph, curr);
  266.         IDelEdge((char *) prev, (char *) curr, ord);
  267.       IDelNode((char *) curr, ord);
  268.         curr = prev;
  269.     }
  270.  
  271.     *top = curr;
  272. } /* scr_remove_ante_links */
  273.  
  274. scr_remove_succ_links(digraph, node, next_node, ord, bot)
  275. DIGRAPH *digraph;
  276. NODE *node, *next_node;
  277. int ord;
  278. NODE **bot;
  279.   /** 
  280.      scr_remove_succ_links follows the chain of successor edges from node 
  281.      through next through the next non-dummy node, deleting all edges and 
  282.      dummy nodes along the way.  When done, it sets bot to the next non-dummy 
  283.      node.
  284.    **/
  285. {
  286.     NODE *curr, *next;
  287.  
  288.     IDelEdge((char *) node, (char *) next_node, ord);
  289.     curr = next_node;
  290.  
  291.     while (Is_dummy(curr))
  292.     {
  293.         next = next_dummy(digraph, curr);
  294.         IDelEdge((char *) curr, (char *) next, ord);
  295.         IDelNode((char *) curr, ord);
  296.         curr = next;
  297.     }
  298.  
  299.     *bot = curr;
  300. } /* scr_remove_succ_links */
  301.